package com.example.system.class13;

/**
 * @Date 2022/8/1
 * @Author Jonathan
 * @Description 是否是平衡二叉树
 */
public class Code02_IsBalanceBT {
    private static int index = 0;

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 8, 12, null, null, null, 4, 3, null, null, 9, null, null};
        Integer[] arr1 = new Integer[]{1, 8, 12, null, null, null, null};
        final Node node = createBST(arr);
        System.out.println("isBalanced:" + isBalanced(node));
        index = 0;
        System.out.println("isBalanced:" + isBalanced(createBST(arr1)));

    }


    public static boolean isBalanced(Node root) {
        return process(root).isBalanced;
    }


    private static Info process(Node x) {
        // base case
        if (x == null) {
            return new Info(true, 0);
        }
        // 左边的信息
        Info left = process(x.left);
        // 右边的信息
        Info right = process(x.right);
        boolean isBalanced = left.isBalanced && right.isBalanced && Math.abs(left.height - right.height) <= 1;
        return new Info(isBalanced, Math.max(left.height, right.height) + 1);
    }


    static class Info {
        private boolean isBalanced;
        private int height;

        public Info(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }


    static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node[" +
                    "value=" + value +
                    ']';
        }
    }

    public static Node createBST(Integer[] arr) {
        if (arr == null || arr.length <= 0) {
            return null;
        }
        return create(arr);
    }

    // 借助全局变量实现
    public static Node create(Integer[] arr) {
        Integer value = arr[index++];
        //System.out.printf("index:%d, arr[index]:%d\n", index, value);
        if (value == null) {
            return null;
        }
        final Node node = new Node(value);
        node.left = create(arr);
        node.right = create(arr);
        return node;
    }
}
